#include<windows.h>
#include"resource.h"
#include<string.h>
#include<stdlib.h>

#define MAX_LEN 100

int urmator[MAX_LEN];
int nrcomparatii, nr, nrfin=0;

//comparatii forta bruta pas cu pas
 void fortabruta(char *p, char *a)
{int M=strlen(p), N=strlen(a);
 int i,j;
 nr=0;
 for (i = 0; i < N; i++)
	for (j = 0; j < M; j++)
		{nr++;
		 if (a[i+j] != p[j]) 
			break;
		}
	 
}

//vectorul de prefixe
void initurm(char *p)
{int i, j, m=strlen(p); 
 urmator[0]=-1; 
 for(i = 0, j = -1; i < m; i++, j++, urmator[i] = j)
	while(j >= 0 && p[i] != p[j])
		j = urmator[j];
} 

void kmppas(HWND hdlg,char *p, char *a,int pas)//p=cuvantul cautat; a=textul in care se cauta;
{static int k, x, i=-1, j=-1, m=strlen(p), n=strlen(a);
 char aux[4];

 initurm(p);
 //sfarsit pas cu pas
 if(pas!=1)
	if(i==strlen(a))
		return;
 //primul pas-afiseaza un spatiu
 if(pas==1)
	{i=-1;
	 j=-1;
	 SendDlgItemMessage(hdlg,IDC_EDIT4,EM_REPLACESEL,0,(LPARAM)" ");
	}
 static int count=0;

    {eticheta:
     i++;
     j++;

	 //sfarsit pas cu pas-afiseaza numarul de comparatii al algoritmilor
     if( i>=strlen(a))
		{SetDlgItemInt(hdlg,IDC_EDIT1,nrcomparatii,TRUE);
		 fortabruta(p,a);
		 nrfin=nrfin+nr;
		 SetDlgItemInt(hdlg,IDC_EDIT3,nrfin,TRUE);
         return;
        }

     count=0;
     nrcomparatii++;
     while(j >= 0 && a[i] != p[j])
		{//afiseaza caractere din cuvantul cautat
		 if(!count)
			{aux[0]=p[j];
             aux[1]='\r';
             aux[2]='\0';                     
             SendDlgItemMessage(hdlg,IDC_EDIT4,EM_REPLACESEL,0,(LPARAM)aux);
             SendDlgItemMessage(hdlg,IDC_EDIT4,EM_REPLACESEL,0,(LPARAM)"\n\r");//rand nou
             
			 //afiseaza spatii pentru a continua de sub caracterele anterioare
			 for(k=0;k<=i-j-1;k++)
			 	 SendDlgItemMessage(hdlg,IDC_EDIT4,EM_REPLACESEL,0,(LPARAM)" \r");
             
			 //afiseaza valorile corespunzatoare din vectorul de prefixe
             for(k=0;k<=j;k++)
				{itoa(urmator[k],aux,10);
                 if(strlen(aux)==1)//daca !=-1
					{aux[1]='\r';
                     aux[2]='\0';
                    }
                 else//daca =-1
					 {aux[2]='\r';
                      aux[3]='\0';
                     }
				 
				 SendDlgItemMessage(hdlg,IDC_EDIT4,EM_REPLACESEL,0,(LPARAM)aux);
                }//end for

             SendDlgItemMessage(hdlg,IDC_EDIT4,EM_REPLACESEL,0,(LPARAM)"\n\r");//rand nou
            }//end if(!count)
		 else
			 nrcomparatii++;

		 count++;                                      
         j=urmator[j];
		 if(j>=0)
			 {//afiseaza spatii pentru a ajunge pe pozitia corespunzatoare pe noul rand
			  for(k=0;k<=i;k++)
					SendDlgItemMessage(hdlg,IDC_EDIT4,EM_REPLACESEL,0,(LPARAM)" \r");
			  
			  //afiseaza caracterul corespunzator in urma nepotrivirii
			  aux[0]=p[j];
			  aux[1]='\r';
			  aux[2]='\0';
			  SendDlgItemMessage(hdlg,IDC_EDIT4,EM_REPLACESEL,0,(LPARAM)aux);
			  SendDlgItemMessage(hdlg,IDC_EDIT4,EM_REPLACESEL,0,(LPARAM)"\n\r");//rand nou
				
			  //afiseaza spatii pentru a continua sub caracterul anterior
			  if(urmator[j]>=0)
				  for(k=0;k<=i;k++)//daca !=-1 
					  SendDlgItemMessage(hdlg,IDC_EDIT4,EM_REPLACESEL,0,(LPARAM)" \r");
			  else
				  for(k=0;k<=i-1;k++)//daca =-1
					  SendDlgItemMessage(hdlg,IDC_EDIT4,EM_REPLACESEL,0,(LPARAM)" \r");
			  
			  //afiseaza indexul corespunzator din vectorul de prefixe
			  itoa(urmator[j],aux,10);
			  if(strlen(aux)==1)//daca !=-1
				  {aux[1]='\r';
				   aux[2]='\0';
				  }
			  else//daca =-1
				  {aux[2]='\r';
				   aux[3]='\0';
				  }
			  SendDlgItemMessage(hdlg,IDC_EDIT4,EM_REPLACESEL,0,(LPARAM)aux);
			  SendDlgItemMessage(hdlg,IDC_EDIT4,EM_REPLACESEL,0,(LPARAM)"\n\r");//rand nou
			 }//end if(j>=0)

            }//end while
	 
	 
     if(count)
		{//afiseaza spatii pentru a ajunge pe pozitia corespunzatoare pe noul rand
		 for(k=0;k<=i-j;k++)
				SendDlgItemMessage(hdlg,IDC_EDIT4,EM_REPLACESEL,0,(LPARAM)" \r");
		
		 if(j>0)
			 //afiseaza caractere din cuvant
		     for(k=0;k<j+1;k++)
				{aux[0]=p[k];
				 aux[1]='\r';
				 aux[2]='\0';
				 SendDlgItemMessage(hdlg,IDC_EDIT4,EM_REPLACESEL,0,(LPARAM)aux);
				}//end for

		}//end if(count)

     if(j==-1)
		 goto eticheta;//in cazul in care nepotrivirea este de la primul caracter
                   
     if(count>2)
		 if(j==0)
			 SendDlgItemMessage(hdlg,IDC_EDIT4,EM_REPLACESEL,0,(LPARAM)"\r");//afiseaza un spatiu
                   
     if(count!=1)
		{//afiseaza caracterul din cuvant
		 aux[0]=p[j];
         aux[1]='\r';
         aux[2]='\0';
         SendDlgItemMessage(hdlg,IDC_EDIT4,EM_REPLACESEL,0,(LPARAM)aux);
        }//end if(count!=1)

     if(j==m-1)//daca s-a ajuns la sfarsitul cuvantului(daca s-a gasit cuvantul)
		{SendDlgItemMessage(hdlg,IDC_EDIT4,EM_REPLACESEL,0,(LPARAM)"-cuvantul s-a gasit incepand cu pozitia \r");
		 itoa(i-j+1,aux,10);
		 aux[strlen(aux)]='\r';
		 aux[strlen(aux)]='\0';
		 SendDlgItemMessage(hdlg,IDC_EDIT4,EM_REPLACESEL,0,(LPARAM)aux);//afiseaza pozitia din text de unde incepe cuvantul
		 SendDlgItemMessage(hdlg,IDC_EDIT4,EM_REPLACESEL,0,(LPARAM)"\n\r");//rand nou
	     
	     //afiseaza spatii pentru a ajunge pe pozitia corespunzatoare
         for(k=0;k<=i-j-1;k++)
			 SendDlgItemMessage(hdlg,IDC_EDIT4,EM_REPLACESEL,0,(LPARAM)" \r");
         
		 //afiseaza vectorul de prefixe
		 for(k=0;k<=j;k++)
			 {itoa(urmator[k],aux,10);
			  if(strlen(aux)==1)//daca !=-1
				  {aux[1]='\r';
                   aux[2]='\0';
                  }
              else//daca =-1
				  {aux[2]='\r';
                   aux[3]='\0';
                  }
              SendDlgItemMessage(hdlg,IDC_EDIT4,EM_REPLACESEL,0,(LPARAM)aux);
             }//end for
         
		 SendDlgItemMessage(hdlg,IDC_EDIT4,EM_REPLACESEL,0,(LPARAM)"\n\r");//rand nou

		 //afiseaza spatii pentru a ajunge pe pozitia corespunzatoare
         for(k=0;k<=i+1;k++)
			 SendDlgItemMessage(hdlg,IDC_EDIT4,EM_REPLACESEL,0,(LPARAM)" \r");

         j=-1;//reinitializare pentru a se relua algoritmul

        }//end if(j==m-1)
           
    }//end eticheta
}